package main

import "fmt"

/*
----------选择排序---------
思路：				9,5,66,1,21,42
1. 从第一个开始，依次跟后面的比较，得出最大或者最小和第一个交换位置    			1,5,66,9,21,42
2. 接着从第二个开始，依次跟后面的比较，得出最大或者最小和第二个交换位置			1,5,66,9,21,42
3. 接着从第三个开始，依次跟后面的比较，得出最大或者最小和第三个交换位置			1,5,9,66,21,42
4. 依次类推到倒数第二个完成

缺点：不管是数组是有序还是无序的，都会选择一遍

平均时间复杂度：O(N^2)
最坏时间复杂度：O(N^2)
空间复杂度: O(1)
稳定性：不稳定

 */

func main() {
	arr := []int{9,5,66,1,21,42}
	fmt.Println(selectSort(arr))
}

func selectSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}

	for i := 0; i < length - 1;i++ {
		minIdx := i
		for j := i + 1; j < length;j++ {
			if arr[minIdx] > arr[j] {
				minIdx = j
			}
		}

		if minIdx != i {
			arr[minIdx], arr[i] = arr[i], arr[minIdx]
		}
	}

	return arr
}
